use serde::de::{self, MapAccess, Visitor};
use serde::Deserialize;
use std::collections::HashMap;

#[derive(Debug, Deserialize)]
struct TestCases {
    #[serde(flatten)]
    test_cases: HashMap<String, Entity>,
}

#[derive(Debug, Deserialize)]
struct Entity {
    #[serde(flatten)]
    connections: Connections,
}

#[derive(Debug)] // No Deserialize here.
struct Connections(Vec<(String, Vec<String>)>);

// the key can be repeated, so we need to implement Deserialize for Connections
impl<'de> Deserialize<'de> for Connections {
    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
    where
        D: de::Deserializer<'de>,
    {
        struct MyVisitor;

        impl<'d> Visitor<'d> for MyVisitor {
            type Value = Vec<(String, Vec<String>)>;

            fn expecting(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
                f.write_str("a fake map of connections")
            }

            fn visit_map<M>(self, mut access: M) -> Result<Self::Value, M::Error>
            where
                M: MapAccess<'d>,
            {
                let mut connections: Vec<(String, Vec<String>)> = Vec::new();
                while let Some((key, value)) = access.next_entry()? {
                    connections.push((key, value));
                }
                Ok(connections)
            }
        }
        Ok(Connections(deserializer.deserialize_map(MyVisitor)?))
    }
}

pub fn count_provinces() -> String {
    let mut res = Vec::<(String, i32)>::new();
    let json_str = std::fs::read_to_string("district.json").unwrap();
    let test_cases: TestCases = serde_json::from_str(&json_str).unwrap();
    for (label, entity) in test_cases.test_cases {
        let mut p: HashMap<String, String> = HashMap::new();
        // init
        for (city, neighbors) in entity.connections.0.iter() {
            p.insert(city.clone(), city.clone());
            for neighbor in neighbors.iter() {
                p.insert(neighbor.clone(), neighbor.clone());
            }
        }
        for (city, neighbors) in entity.connections.0.iter() {
            for neighbor in neighbors.iter() {
                union(&city, &neighbor, &mut p);
            }
        }
        let mut cnt = 0;
        for (k, v) in p.iter() {
            if k == v {
                cnt += 1;
            }
        }
        res.push((label, cnt));
    }
    // sort by label
    res.sort_by(|a, b| a.0.cmp(&b.0));
    let mut res_str = String::new();
    for (_label, cnt) in res.iter() {
        if !res_str.is_empty() {
            res_str.push(',');
        }
        res_str.push_str(&cnt.to_string());
    }
    res_str
}

// Union set: find
fn find(i: &String, p: &mut HashMap<String, String>) -> String {
    let pi = p[i].clone();
    if pi == *i {
        i.clone()
    } else {
        let root = find(&pi, p);
        p.insert(i.clone(), root.clone());
        root
    }
}

// Union set: union
fn union(i: &String, j: &String, p: &mut HashMap<String, String>) {
    let root_i = find(i, p);
    let root_j = find(j, p);
    if root_i != root_j {
        p.insert(root_j, root_i);
    }
}
